import heapq
import coordinates

def a_star_search(map, start, goal, use_unexplored_tiles=False):

    # TODO: Make this consider fighting its way through squishy obstacles

    class node:
        def __init__(self, position, parent_node, predicted_cost, existing_cost):
            self.position = position
            self.parent_node = parent_node
            self.predicted_cost = predicted_cost
            self.existing_cost = existing_cost


    def expand_tile(parent_node):
        x = parent_node.position.x
        y = parent_node.position.y

        # explore west
        if x > 0:
            if use_unexplored_tiles or map[x-1][y].explored:
                new_pos = coordinates.coordinate(x-1, y)
                if new_pos == goal:
                    return parent_node

                if not map[x-1][y].blocked:
                    if expanded.count(new_pos) == 0:
                        predicted_cost = coordinates.manhattan_dist(new_pos, goal)
                        n = node(position=new_pos, parent_node=parent_node, predicted_cost=predicted_cost, existing_cost=parent_node.existing_cost+1)
                        heapq.heappush(un_expanded, (predicted_cost+parent_node.existing_cost, n))

        # explore east
        if x < width:
            if use_unexplored_tiles or map[x+1][y].explored:
                new_pos = coordinates.coordinate(x+1, y)
                if new_pos == goal:
                    return parent_node

                if not map[x+1][y].blocked:
                    if expanded.count(new_pos) == 0:
                        predicted_cost = coordinates.manhattan_dist(new_pos, goal)
                        n = node(position=new_pos, parent_node=parent_node, predicted_cost=predicted_cost, existing_cost=parent_node.existing_cost+1)
                        heapq.heappush(un_expanded, (predicted_cost+parent_node.existing_cost, n))

        # explore north
        if y > 0:
            if use_unexplored_tiles or map[x][y-1].explored:
                new_pos = coordinates.coordinate(x, y-1)
                if new_pos == goal:
                    return parent_node

                if not map[x][y-1].blocked:
                    if expanded.count(new_pos) == 0:
                        predicted_cost = coordinates.manhattan_dist(new_pos, goal)
                        n = node(position=new_pos, parent_node=parent_node, predicted_cost=predicted_cost, existing_cost=parent_node.existing_cost+1)
                        heapq.heappush(un_expanded, (predicted_cost+parent_node.existing_cost, n))

        # explore south
        if y < height:
            if use_unexplored_tiles or map[x][y+1].explored:
                new_pos = coordinates.coordinate(x, y+1)
                if new_pos == goal:
                    return parent_node

                if not map[x][y+1].blocked:
                    if expanded.count(new_pos) == 0:
                        predicted_cost = coordinates.manhattan_dist(new_pos, goal)
                        n = node(position=new_pos, parent_node=parent_node, predicted_cost=predicted_cost, existing_cost=parent_node.existing_cost+1)
                        heapq.heappush(un_expanded, (predicted_cost+parent_node.existing_cost, n))

        return None

    width = len(map)
    height = len(map[0])


    # All nodes which have been seen but not expanded
    un_expanded = []

    # All nodes that have been expanded
    expanded = []


    estimated_cost = coordinates.manhattan_dist(start, goal)
    root_node = node(start, None, estimated_cost, 0)
    heapq.heappush(un_expanded, (estimated_cost, root_node))

    while len(un_expanded) > 0:
        n = heapq.heappop(un_expanded)
        # if goal == n[1].position:
        #     return n[1]
        expanded.append(n[1].position)
        if expand_tile(n[1]) is not None:
            path = [n[1].position]
            parent = n[1].parent_node
            cost = 0
            while parent is not None:
                path.append(parent.position)
                parent = parent.parent_node
                cost += 1

            path.reverse()
            return path

    return None
